// ****************************计数排序****************************************************
/**
 * 适用于数据量特别大，但数据值比较集中
 * 1. 创建一个辅助数组，数组范围为 0-max数值 共max+1个数值。数组下标对应相应的原数组值
 * 2. 遍历原数组，读取的值就在对应的辅助数组下标处的数组值加1
 * 3. 完成好的辅助数组记录个所有值出现的次数，展开就是排好序的数组了
 * 4. 这种排序没有发生比较；时间复杂度O(n+k)，空间复杂度O(n+k)
 * eg：
 *      原数组[0,1,2,3,1,1,0,4,0,1,2,2,3,3,2,5]
 *      辅助数组值：    [3,4,4,3,1,1] 记录了0-5分别出现的次数 k
 *      辅助数组下标：   0,1,2,3,4,5 包括了所有原数组可能出现的值
 *      展开辅助数组：  [0,0,0,1,1,1,1,2,2,2,2,3,3,3,4,5] 已经排序完成的结果数组 n
 */
function countSort(arr) {
  //寻找原数组arr的最大值
  let max = findMax(arr)
  //初始化计数数组
  let countArr = new Array(max+1)
  for(let i = 0; i <= countArr.length-1; i++) {
      countArr[i] = 0
  }
  //完成计数数组
  for(let i = 0; i <= arr.length - 1; i++) {
      countArr[arr[i]]++
  }
  //展开计数数组
  for(let i = 0, j = 0; i <= countArr.length-1; i++) {
      while(countArr[i] > 0) {
          arr[j] = i
          countArr[i]--
          j++
      }
  }
}
  function findMax(arr) {
      let max = arr[0];
      for(let i = 1; i <= arr.length - 1; i++) {
          if(arr[i] > max) {
              max = arr[i]
          }
      }
      return max;
  }

//测试用例
let arr = [2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9]
countSort(arr)
console.log(arr);

